package top.datacluster.basic.algorithm.leetcode.dynamic;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

public class LeetCode1473 {

    public List<List<Integer>> pathWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid[0][0] == 1){
            return new ArrayList<>();
        }
        LinkedList<List<Integer>> path = new LinkedList<>();
        int i = 0;
        int j = 0;
        List<Integer> p;
        while (i < obstacleGrid.length - 1 || j < obstacleGrid[0].length - 1){
            if (j + 1 < obstacleGrid[0].length && obstacleGrid[i][j + 1] != 1){

                p = new ArrayList<>();
                p.add(i);
                p.add(j);
                path.offerLast(p);
                j++;
            }else if (i + 1 < obstacleGrid.length && obstacleGrid[i + 1][j] != 1){

                p = new ArrayList<>();
                p.add(i);
                p.add(j);
                path.offerLast(p);
                i++;
            }else{
                obstacleGrid[i][j] = 1;
                if (path.isEmpty()){
                    return new ArrayList<>();
                }
                i = path.peekLast().get(0);
                j = path.pollLast().get(1);
            }
        }
        List<List<Integer>> result = new ArrayList<>();
        while (!path.isEmpty()){

            result.add(path.pollFirst());
        }
        return result;
    }

    public static void main(String[] args) {
        int[][] test = new int[][]{{0,0,0,0,0},{0,0,0,0,1},{0,0,0,1,0},{0,0,0,0,0}};
        new LeetCode1473().pathWithObstacles(test);
    }
}
